package Year22_Month06.day01;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

public class 二叉树的层序遍历_BFS {
    public List<List<Integer>> levelOrder(TreeNode root) {
        Queue<TreeNode> queue = new LinkedList<>();
        List<List<Integer>> list = new ArrayList<>();//作为返回列表
        if(root != null){
            queue.add(root);
        }
        //要保证主队列不能为空
        while(!queue.isEmpty()){
            int count = queue.size();//计数器来记录当前这一层有多少个节点
            List<Integer> mylist = new ArrayList<>();
            while(count != 0){//遍历这一层所有的节点
                TreeNode key = queue.poll();
                if(key.left != null){
                    queue.add(key.left);
                }
                if(key.right != null){
                    queue.add(key.right);
                }
                mylist.add(key.val);
                count--;
            }
            list.add(mylist);
        }
        return list;
    }
}

/*
public List<List<Integer>> levelOrder(TreeNode root) {
        Queue<TreeNode> queue1 = new LinkedList<>();//作为主队列
        Queue<TreeNode> queue2 = new LinkedList<>();//作为副队列
        List<List<Integer>> list = new ArrayList<>();//作为返回列表
        if(root != null){
            queue1.add(root);
        }
        //要保证主队列不能为空
        while(!queue1.isEmpty()){
            List<Integer> mylist = new ArrayList<>();
            while(!queue1.isEmpty()){
                //然后把主队列里面所有节点的左子树和右子树全部加入副队列里面
                TreeNode key = queue1.poll();
                if(key.left != null){
                    queue2.add(key.left);
                }
                if(key.right != null){
                    queue2.add(key.right);
                }
                mylist.add(key.val);
            }
            list.add(mylist);
            //此时主队列为空，那么交换主队列和副队列
            Queue<TreeNode> tmp = queue1;
            queue1 = queue2;
            queue2 = tmp;
        }
        return list;
    }
 */
